package other;

import java.util.HashMap;

public class Lru1 {

    //实现双向链表
    private LinkedList list;
    //保证O(1)查询
    private HashMap<Integer, Node> map;
    private int capacity;

    public Lru1(int capacity) {
        this.list = new LinkedList();
        this.map = new HashMap<>();
        this.capacity = capacity;
    }

    // 读的时候移动到队尾
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node n = map.get(key);
        list.moveToTail(n);
        return n.val;
    }

    //写的时候超出容量删除
    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            Node n = new Node(key, value);
            map.put(key, n);
            list.addToTail(n);

            if (map.size() > capacity) {
                Node rmv = list.removeHead();
                map.remove(rmv.key);
            }
        } else {
            Node n = map.get(key);
            n.val = value;
            list.moveToTail(n);
        }
    }
}

class LinkedList {

    private Node head;
    private Node tail;

    public LinkedList() {
        this.head = null;
        this.tail = null;
    }

    public void moveToTail(Node node) {
        // 删除节点
        if (node == null || node == tail)
            return;
        if (head == node) {
            head = node.next;
            head.pre = null;
        } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        // 组装节点
        tail.next = node;
        node.pre = tail;
        node.next = null;
        tail = tail.next;
    }

    public void addToTail(Node n) {
        if (n == null) return;
        // 添加新的节点
        if (head == null) {
            head = n;
            tail = n;
        } else {
            tail.next = n;
            n.pre = tail;
            tail = n;
        }
    }

    public Node removeHead() {
        // 删除头部（最老的）节点
        if (head == null) return null;
        Node n = head;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.pre = null;
        }
        return n;
    }
}

// Map
class Node {

    public Node pre;
    public Node next;
    public int key;
    public int val;

    public Node(int k, int v) {
        this.key = k;
        this.val = v;
        this.pre = null;
        this.next = null;
    }

}
